Public key cryptography is typically used for secure communications over the Internet, for example, to distribute secret keys used in cryptographic algorithms. Public key cryptography is also used in digital signatures to authenticate the origin of data and protect the integrity of that data. Commonly used public key algorithms include Rivert, Shamir, Aldeman (RSA) and Diffie-Hellman key exchange (DH). The public key algorithms may be used to authenticate keys for encryption algorithms such as the Data Encryption Standard (DES) and Advanced Encryption Standard (AES).
RSA and DH provide security based on the use of number theory. RSA is based on factoring the product of two large prime numbers. DH is based on discrete logarithm for finite groups. Typically, public key systems use 1024-bit parameters for RSA and DH.
In protocols such as RSA or DH the main operation is a large modular exponentiation with operands in the range of 512 to 4096 bits (or higher for ultra-secure applications). In modular arithmetic, the result of an operation is a number (N) in the range between 0 and the modulus (M). A number N is congruent with X (mod Y), where N is the remainder after X is divided by Y, for example, if X=7 and Y=3. N=7 (mod 3)=1, that is, the remainder is 1 when 7 is divided by 3 so N=1 is congruent with 7 (mod 3).
Modular exponentiation algorithms may perform repeated modular squaring and/or multiplication operations, which include multiplication operations followed by modular reduction of the product. The modular reduction may be performed by a variety of techniques such as Montgomery reduction or Barrett's reduction.
Although the following Detailed Description will proceed with reference being made to illustrative embodiments, many alternatives, modifications, and variations thereof will be apparent to those skilled in the art.